package kyssion.leetcode.num51_100;

public class code74_搜索二维矩阵 {

    public static void main(String[] args) {
        System.out.println(new code74_搜索二维矩阵().searchMatrix(
                new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,50}},34
        ));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0||matrix[0].length==0){
            return false;
        }
        int left = 0;
        int right = matrix.length - 1;
        while (left < right) {
            int midle = (left + right) >> 1;
            if (matrix[midle][0] < target) {
                left = midle + 1;
            } else if (matrix[midle][0] > target) {
                right = midle - 1;
            } else {
                return true;
            }
        }
        if (matrix[left][0] > target) {
            if (left == 0) {
                return false;
            }
            left--;
        } else if (matrix[left][0] == target) {
            return true;
        }
        int index = left;
        left = 0;
        right = matrix[left].length-1;
        while (left <= right) {
            int midle = (left + right) >> 1;
            if (matrix[index][midle] < target) {
                left = midle + 1;
            } else if (matrix[index][midle] > target) {
                right = midle - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
